/*
这是一个通用的中序线索二叉树的实现

*/

#include "bin_thread_tree.h"
#include <stdlib.h>
#include <string.h>

// link 线索指针指向左右孩子, thread 线索指针指向前驱或后继
typedef enum { child, thread } tag;

// 节点
struct bi_Node_t {
  bi_node left, right;
  tag l_tag, r_tag; // 每个节点增加两个标记域
  size_t size;      // 数组数据大小
  char data[];      // 数据指针,灵活数组类型
};

// 搜索树结构
struct bi_tree_t {
  bi_node root;
  cmp_func_t *func_cmp;
  get_key_func_t *func_get_key;
};

// --------------私有辅组函数声明----------------------------------------

static void *_search(bitree btree, const bi_node node, const void *key);

static bool _insert(bitree btree, bi_node *pnode, const void *data,
                    size_t size);

static bool _delete(bitree btree, bi_node *pnode, const void *key);

static void _clear(bi_node node);

static bi_node _detach_min(bi_node *pnode);

static int _in_order(bi_node node, bool (*action)(void *data));

static int _pre_order(bi_node node, bool (*action)(void *data));

static int _post_order(bi_node node, bool (*action)(void *data));

static void _thread(bi_node node, bi_node *pre_node);

static void _in_order_thread(bi_node node, bool (*action)(void *data));

static void _rev_in_order_thread(bi_node node, bool (*action)(void *data));

// -------------------------------------------------------------------

// 默认获取节点上数据的方法,如果你的data结构比较复杂,请自定义
const void *default_get_key(const void *data) { return data; }

// 创建线索二叉树
bitree bit_tree_create(cmp_func_t *cmp, get_key_func_t *getKey) {
  bitree tree = NULL;

  if (cmp != NULL)
    tree = malloc(sizeof(struct bi_tree_t));

  if (tree != NULL) {
    tree->root = NULL;
    tree->func_cmp = cmp;
    tree->func_get_key = (getKey == NULL) ? default_get_key : getKey;
  }

  return tree;
}

/* 向二叉树中插入数据 */
bool bit_tree_insert(bitree btree, const void *data, size_t size) {
  if (btree == NULL || data == NULL || size == 0)
    return false;

  return _insert(btree, &(btree->root), data, size);
}

/* 在二叉树找查找 */
bool bit_tree_delete(bitree btree, const void *key) {
  if (btree == NULL || key == NULL)
    return false;

  return _delete(btree, &(btree->root), key);
}

/* 删除二叉树中的指定数据 */
const void *bit_tree_search(bitree btree, const void *key) {
  if (btree == NULL || key == NULL)
    return NULL;

  return _search(btree, btree->root, key);
}

/* 清空树节点,保留tree对象 */
void bit_tree_clear(bitree btree) {
  if (btree != NULL) {
    _clear(btree->root);
    btree->root = NULL;
  }
}

/* 清空树节点,释放tree对象 */
void bit_tree_destory(bitree btree) {
  if (btree != NULL) {
    bit_tree_clear(btree);
    free(btree);
  }
}

// 中序遍历 LNR 从小到大
int bit_tree_in_order(bitree btree, bool (*action)(void *data)) {
  if (btree == NULL || action == NULL)
    return 0;

  return _in_order(btree->root, action);
}

// 前序遍历 NLR
int bit_tree_pre_order(bitree btree, bool (*action)(void *data)) {
  if (btree == NULL || action == NULL)
    return 0;

  return _pre_order(btree->root, action);
}

// 后序遍历 LRN
int bit_tree_post_order(bitree btree, bool (*action)(void *data)) {
  if (btree == NULL || action == NULL)
    return 0;

  return _post_order(btree->root, action);
}

// 对二叉树进行中序线索化
void bit_tree_thread(bitree btree) {
  if (btree == NULL)
    return;
  bi_node pre_node = NULL; // 始终存放中序遍历的前一个节点

  _thread(btree->root, &pre_node);

  // 处理遍历的最后一个节点
  if (pre_node->right == NULL)
    pre_node->r_tag = thread;
}

// 中序线索后继遍历二叉树
void bit_tree_in_order_thread(bitree btree, bool (*action)(void *data)) {
  if (btree == NULL || action == NULL)
    return;

  _in_order_thread(btree->root, action);
}

// 中序线索前驱遍历二叉树
void bit_tree_rev_in_order_thread(bitree btree, bool (*action)(void *data)) {
  if (btree == NULL || action == NULL)
    return;

  _rev_in_order_thread(btree->root, action);
}

// ---------------------------私有辅助函数----------------------------------

static void _thread(bi_node node, bi_node *pre_node) {
  if (node) {
    //递归左子树
    _thread(node->left, pre_node);

    if (node->left == NULL) { // 左孩子节点是空,建立前驱
      node->l_tag = thread;   // 前驱
      node->left = *pre_node; // 刚才访问过的节点
    }

    // 前驱的右节点为空, 建立后继
    if (*pre_node != NULL && (*pre_node)->right == NULL) {
      (*pre_node)->r_tag = thread; // 后继
      (*pre_node)->right = node;   // 即将要访问的节点
    }

    *pre_node = node;

    // 递归右子树
    _thread(node->right, pre_node);
  }
}

// 中序线索二叉树遍历
static void _in_order_thread(bi_node node, bool (*action)(void *data)) {

  while (node != NULL) {
    // 找到最小左节点
    while (node->left != NULL && node->l_tag == child)
      node = node->left;

    (*action)(node->data); // 访问最小节点

    // 找中序后继, 访问之
    while (node->right != NULL && node->r_tag == thread) {
      node = node->right;
      (*action)(node->data);
    }
    //该结点有右子树，node->r_tag==child,左子树已经遍历完了，这里进入右子树
    node = node->right;
  }
}

// 逆向中序线索二叉树遍历
static void _rev_in_order_thread(bi_node node, bool (*action)(void *data)) {

  while (node != NULL) {
    // 找到最大右节点
    while (node->right != NULL && node->r_tag == child)
      node = node->right;

    (*action)(node->data); // 访问最大右节点

    // 中序前驱, 访问之
    while (node->left != NULL && node->l_tag == thread) {
      node = node->left;
      (*action)(node->data);
    }
    //该结点有左子树，node->l_tag==child,遍历左子树
    node = node->left;
  }
}

/*
  查找key
*/

static void *_search(bitree btree, const bi_node node, const void *key) {
  if (node == NULL)
    return NULL;

  int cmp_res = btree->func_cmp(key, btree->func_get_key(node->data));
  if (cmp_res < 0)
    return _search(btree, node->left, key);
  else if (cmp_res > 0)
    return _search(btree, node->right, key);
  else
    return node->data;
}

/*
  插入函数, 搜索二叉树插入
*/
static bool _insert(bitree btree, bi_node *pnode, const void *data,
                    size_t size) {
  bi_node p = *pnode;

  if (p == NULL) { // 新节点
                   // 填充灵活数组,一定要记得加size空间大小
    if ((p = malloc(sizeof(struct bi_Node_t) + size)) != NULL) {
      p->left = p->right = NULL;
      memcpy(p->data, data, size);
      p->size = size;
      p->l_tag = p->r_tag = child; // 默认都是子节点
      *pnode = p;
      return true;
    } else
      return false;
  } else {
    const void *key1 = btree->func_get_key(data);
    const void *key2 = btree->func_get_key(p->data);
    if (btree->func_cmp(key1, key2) < 0)
      return _insert(btree, &(p->left), data, size);
    else
      return _insert(btree, &(p->right), data, size);
  }
}

/*
  删除辅助函数
*/
static bool _delete(bitree btree, bi_node *pnode, const void *key) {
  bi_node node = *pnode;
  if (node == NULL)
    return false;

  int cmp_res = btree->func_cmp(key, btree->func_get_key(node->data));

  if (cmp_res < 0) // 递归左子树查找
    return _delete(btree, &(node->left), key);
  else if (cmp_res > 0) // 递归右子树查找
    return _delete(btree, &(node->right), key);
  else {
    if (node->left == NULL) // 仅有右节点
      *pnode = node->right;
    else if (node->right == NULL) // 仅有左节点
      *pnode = node->left;
    else {
      bi_node pmin = _detach_min(&(node->right)); // 找右子树中的最小值
      *pnode = pmin;                              // 替换将被删除的节点
      pmin->left = node->left;                    // 修复左右分支
      pmin->right = node->right;
    }
  }

  free(node);
  return true;
}

/*
这是一个删除辅助函数, 以将要被删除的节点n作为根节点,该函数会找到它的右子树中
最小值节点m,然后使用m的右子树替换m,并将m节点返回
*/
static bi_node _detach_min(bi_node *pnode) {
  bi_node node = *pnode;
  if (node == NULL)
    return NULL;
  else if (node->left != NULL)
    return _detach_min(&(node->left));
  else {
    *pnode = node->right; // 整体提升最小值的右子树到最小值位置
    return node;          // 返回最小值节点
  }
}

// 左右孩子均可能被当作线索使用,要过滤一下
static void _clear(bi_node node) {
  if (node != NULL) {
    if (node->l_tag == child)
      _clear(node->left);
    if (node->r_tag == child)
      _clear(node->right);

    free(node);
  }
}

static int _in_order(bi_node node, bool (*action)(void *data)) {
  int count = 0;
  if (node == NULL)
    return 0;

  count = _in_order(node->left, action);
  // root 节点
  if (action(node->data))
    ++count;

  count += _in_order(node->right, action);
  return count;
}

static int _pre_order(bi_node node, bool (*action)(void *data)) {
  int count = 0;
  if (node == NULL)
    return 0;

  if (action(node->data))
    ++count;

  count = _pre_order(node->left, action);
  count += _pre_order(node->right, action);
  return count;
}

static int _post_order(bi_node node, bool (*action)(void *data)) {
  int count = 0;
  if (node == NULL)
    return 0;

  count = _post_order(node->left, action);
  count += _post_order(node->right, action);

  if (action(node->data))
    ++count;

  return count;
}
